package homework;

public class zy04 {
	public static  void main(String[] args) {
		String s = findLongest("dajlskldjsalkdjsalkda","djaskldjlsalk");
		System.out.println(s);
	}
	
	public static String findLongest(String str1, String str2) {
		int m = str1.length();
        int k = str2.length();
        int maxLength = 0;
        int endIndex = -1;
        int[][] dp = new int[m + 1][k + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= k; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > maxLength) {
                        maxLength = dp[i][j];
                        endIndex = i - 1;
                    }
                }
            }
        }
        if (maxLength > 0) {
            return str1.substring(endIndex - maxLength + 1, endIndex + 1);
        } else {
            return "";
        }
	}
}
